package com.mzy.linear_struct;

import sun.reflect.generics.tree.Tree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

/**
 * @Author: codermzy
 * @Date: 2024/03/31/20:16
 * @Description:
 */
public class MyHashTable<V> {

    private Node<String, V>[] table;

    private int capacity;

    private final float loadFactor;
    private int size;


    public MyHashTable() {
        capacity = 7;
        loadFactor = 0.75f;
        table = new Node[capacity];
        size = 0;
    }


    public void put(String key, V value) {
        int index = hash(key, capacity);
        Node<String, V> newNode = new Node<>(key, value, null);
        boolean isUpdate = false;
        // 如果当前位置为空直接添加
        if (table[index] == null) {
            table[index] = newNode;
        } else { // 否则用链表连接
            Node<String, V> bucket = table[index];
            // 判断是否有这个key， 如果有就执行更新
            while (bucket != null) {
                if (newNode.equals(bucket)) {
                    bucket.value = value;
                    isUpdate = true;
                    break;
                }
                bucket = bucket.next;
            }

            // 头插法插入链表
            newNode.next = table[index];
            table[index] = newNode;

        }
        // 更新大小
        if (!isUpdate) {
            size++;

            // 判断是否需要扩容
            float curLoad = (float) size / capacity;
            if (curLoad > loadFactor) {
                int newCapacity = capacity * 2;

                // 执行扩容
                resize(newCapacity);
            }
        }


    }

    private void resize(int newCapacity) {
        // 判断新的容量是否是质数
        int newLength = newCapacity;
        if (!isPrimer(newCapacity)) { // 如果不是
            newLength = lookupPrimer(newCapacity);
            if(newLength < 7) {
                newLength = 7;
            }
        }

        Node<String, V>[] oldTab = table;
        capacity = newLength;
        table = new Node[newLength];
        size = 0;
        // 遍历每个桶
        for (Node<String, V> bucket : oldTab) {
            // 把桶中的元素重新置入
            while (bucket != null) {
                put(bucket.key, bucket.value);
                bucket = bucket.next;
            }
        }
    }


    public V get(String key) {
        // 获取桶下标
        int index = hash(key, capacity);

        Node<String, V> bucket = table[index];
        while (bucket != null) {
            // 逐个遍历查找 key 值一样的返回
            if (bucket.key.equals(key)) {
                return bucket.value;
            }
            bucket = bucket.next;
        }
        // 没有找到
        return null;
    }


    public V remove(String key) {
        int index = hash(key, capacity);
        Node<String, V> bucket = table[index];

        // 桶位置一个元素也没有直接删除
        if (bucket == null) {
            return null;
        }
        // 记录上一个元素，为后续删除使用
        Node<String, V> prev = null;
        while (bucket != null) {

            // 找到删除的元素了
            if (bucket.key.equals(key)) {
                V removeValue = null;
                // 执行删除
                if (prev == null) { // 代表删除的元素在一个节点上，直接删除
                    if (bucket.next != null) { // 如果当前位置的元素后面还有元素，则直接指向下一个
                        removeValue = bucket.value;
                        table[index] = bucket.next;
                    } else { // 第一次删除
                        removeValue = bucket.value;
                        table[index] = null;
                    }
                } else { // 删除中间的元素或最后一个元素
                    removeValue = bucket.value;
                    prev.next = bucket.next;

                }
                size--;

                // 判断是否需要缩容
                float curLoad = (float) size / capacity;
                if (curLoad < 0.25 && capacity > 7) {
                    int newCapacity = capacity / 2;

                    resize(newCapacity);
                }

                return removeValue;
            }
            prev = bucket;
            bucket = bucket.next;
        }


        return null;
    }

    private int lookupPrimer(int newCapacity) {
        // while (!isPrimer(newCapacity)){
        //     newCapacity++;
        // }
        for (int i = newCapacity; i < Integer.MAX_VALUE; i++) {
            if (isPrimer(i)) {
                return i;
            }
        }
        return newCapacity;
    }

    private boolean isPrimer(int num) {

        if (num <= 1) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }


    static class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next;

        public Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final String toString() {
            return key + "=" + value;
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node<?, ?> node = (Node<?, ?>) o;
            return key.equals((node.key));
        }

        @Override
        public int hashCode() {
            return Objects.hash(key, value, next);
        }
    }

    public static int hash(String key, int max) {
        long hashCode = 0;
        for (int i = 0; i < key.length(); i++) {
            hashCode = 31 * hashCode + key.charAt(i);
        }

        return (int) (hashCode % max);
    }

    public static void main(String[] args) {
        // System.out.println(hash("abc", 8));
        // System.out.println(hash("cba", 8));
        // System.out.println(hash("nba", 8));
        MyHashTable<Integer> hashTable = new MyHashTable<>();

        hashTable.put("ghi", 1);
        hashTable.put("jkl", 2);
        hashTable.put("cab", 3);
        hashTable.put("abc", 4);
        hashTable.put("cda", 5);
        hashTable.put("yzm", 6);
        hashTable.put("mzy", 7);
        hashTable.put("ijk", 8);
        hashTable.put("kop", 9);
        hashTable.put("pok", 10);
        hashTable.put("lsr", 11);

        // System.out.println(hashTable.remove("ghi"));
        // System.out.println(hashTable.get("ghi"));
        // System.out.println(hashTable.get("jkl"));
        // System.out.println(hashTable.get("cab"));
        // System.out.println(hashTable.get("abc"));
        // System.out.println(hashTable.get("qmf"));
        System.out.println(hashTable.remove("yzm"));
        System.out.println(hashTable.remove("ghi"));
        System.out.println(hashTable.remove("jkl"));
        System.out.println(hashTable.remove("cab"));
        System.out.println(hashTable.remove("pok"));
        System.out.println(hashTable.remove("abc"));
        System.out.println(hashTable.remove("lsr"));

    }

    // public static void main(String[] args) {
    //     final int max = 16; // 假设最大值为1000
    //     Set<String> seenHashes = new HashSet<>();
    //     Set<String> collidingKeys = new HashSet<>();
    //
    //     for (int i = 0; i < Integer.MAX_VALUE; i++) { // 尝试大量不同的字符串
    //         String key = Integer.toString(i);
    //         int hashValue = hash(key, max);
    //         if (seenHashes.contains(hashValue)) {
    //             collidingKeys.add(key);
    //             System.out.println("Found collision for hash value " + hashValue + ": " + collidingKeys);
    //             break; // 找到冲突后退出循环
    //         }
    //     }
    // }
}
